package de.unibi.comet.fa;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map.Entry;

import de.unibi.comet.util.BitArray;
import de.unibi.comet.util.Log;

public class CDFA {
	private List<int[]> transitionTable;
	private List<Integer> outputTable;
	private List<Double> outputProbabilities;
	
// 	private List<CDFANode> nodeTable; 
	private Alphabet alphabet;
	
	public CDFA(Alphabet alphabet, List<int[]> transitionTable, List<Integer> outputTable) {
		this.alphabet = alphabet;
		this.transitionTable = transitionTable;
		this.outputTable = outputTable;
		this.outputProbabilities = null;
	}
	
	/** Count matches.
	 *  @return Returns number of times the automaton was in an accept state.
	 *     Returns -1 if string led to an invalid state. */
	public int countMatchesDFA(String s) {
		Log.getInstance().startTimer();
		int unknownIndex = alphabet.getIndex('#');
		
		int node = 0;
		int count = outputTable.get(0);
		for (int i=0; i<s.length(); ++i) {
			int c = alphabet.getIndex(s.charAt(i));
			// map all other (those not in the pattern) characters onto #
			if (c<0) {
				if (unknownIndex>=0) c=unknownIndex;
				else throw new IllegalArgumentException(String.format("Unknown character \"%s\" encountered", c));
			}
			
			node = transitionTable.get(node)[c];
			if (node<0) return -1;
			
			// Log.getInstance().printInsane(String.format("%d(%s): %d", i, c, node.getIndex()));
			count+=outputTable.get(node);
//			if (node.getOutput()>0) {
//				Log.getInstance().printInsane(String.format("m %d (state: %d)", i, node.getIndex()));
//			}
		}
		Log.getInstance().stopTimer("dfa matching");
		return count;
	}
	
	
	static private int gcd(int a, int b) {
		if (a<b) return gcd(b,a);
		while (b!=0) {
			int tmp=b;
			b=a%b;
			a=tmp;
		}
		return a;
	}

	public int analysePeriodicity() {
		int result = 0;
		// loop over all states and analyze for each its periodicity
		for (int state=0; state<transitionTable.size(); ++state) {
			List<Integer> tmpList = new ArrayList<Integer>();

			int period = -1;
			HashSet<Integer> reachable = new HashSet<Integer>();
			reachable.add(state);
			int n = 0;
			while ((period!=1) && (n<1000)) {
				HashSet<Integer> nextReachable = new HashSet<Integer>();
				for (int i : reachable) {
					for (int j : transitionTable.get(i)) nextReachable.add(j);
				}
				++n;
				reachable=nextReachable;
				if (reachable.contains(state)) {
					if (period==-1) {
						period=n;
					} else {
						period=gcd(n,period);
					}
					tmpList.add(n);
				}
			}
			StringBuffer sb = new StringBuffer();
			sb.append(String.format("%d: %d (", state, period));
			for (int i : tmpList) {
				sb.append(i);
				sb.append(',');
			}
			sb.append(')');
			System.out.println(sb.toString());
			if (period!=1) ++result;
		}
		return result;
	}

	/** Naive (slow) approach. */
	public Partition analyseAsymptoticEquivalence() {
		// determinte final states
		BitArray finalStates = new BitArray(transitionTable.size());
		for (int state=0; state<outputTable.size(); ++state) {
			if (outputTable.get(state)==0) continue;
			if (outputTable.get(state)==1) {
				finalStates.set(state, true);
			} else {
				throw new IllegalStateException("Not implemented for output(state)>1");
			}
		}
		
		// for each state the lengths of the strings leading to a final state
		BitArray[] lengthsArray = new BitArray[transitionTable.size()];
		final int maxLength = 63;
		
		// loop over all states and analyze for each its periodicity
		for (int state=0; state<transitionTable.size(); ++state) {
			// set of states currently active
			BitArray stateSet = new BitArray(transitionTable.size());
			stateSet.set(state, true);
			// possible lengths of strings leading from current state to a final state
			BitArray lengths = new BitArray(maxLength+1);
			if (finalStates.get(state)) lengths.set(0, true);
			
			// true if the state does not change any more
			boolean stable = false;
			for (int i=1; i<=maxLength; ++i) {
				// update state set
				if (!stable) {
					BitArray newStateSet = new BitArray(transitionTable.size());
					int sourceState = -1;
					for (boolean b : stateSet) {
						++sourceState;
						if (!b) continue;
						for (int targetState : transitionTable.get(sourceState)) newStateSet.set(targetState, true); 
					}
					if (newStateSet.equals(stateSet)) {
						stable=true;
					} else {
						stateSet=newStateSet;
					}
				}
				// check if we are in a final state
				BitArray tmp = new BitArray(stateSet);
				tmp.and(finalStates);
				if (!tmp.allZero()) lengths.set(i, true);
			}
			if (!stable) throw new IllegalStateException("State set did not stabelize, increase \"maxLength\"");
			lengthsArray[state]=lengths;
			
			StringBuffer sb = new StringBuffer();
			sb.append(String.format("%d: ", state));
			int m=maxLength;
			for (; m>=1; --m) {
				if (!lengths.get(m-1)) break;
			}
			int n = 0;
			for (boolean b : lengths) {
				if (b) sb.append(String.format("%d,", n));
				++n;
				if (n>m) break;
			}
			sb.append("...");
			System.out.println(sb.toString());
		}
		return new Partition(Arrays.asList(lengthsArray));
	}
	
	/** Annotates the output states belonging to the given strings with the 
	  * given probabilities.*/
	public void setOutputProbabilities(List<ProbabilisticString> l) {
		int stateCount = transitionTable.size();
		// initialize table of output probabilities
		outputProbabilities = new ArrayList<Double>(stateCount);
		for (int i=0; i<stateCount; ++i) outputProbabilities.add(1.0);
		// set output probabilities according to given list
		for (ProbabilisticString ps : l) {
			// determine output state corresponding to string...
			int state = 0;
			for (char c : ps.getString().toCharArray()) {
				state = this.transitionTable.get(state)[alphabet.getIndex(c)];
			}
			if (outputTable.get(state)==0) throw new IllegalStateException("Not an output state!");
			outputProbabilities.set(state, ps.getProbability());
		}
	}
	
	public MarkovAdditiveChain createMAC(double[] characterDist) {
		int stateCount = transitionTable.size();
		@SuppressWarnings("unchecked")
		HashMap<Integer, Double>[] preImageList = new HashMap[stateCount];
		
		for (int i=0; i<stateCount; ++i) {
			preImageList[i]=new HashMap<Integer, Double>();
		}	
		
		int source = 0;
		for (int[] transitions : transitionTable) {
			for (int c=0; c<transitions.length; ++c) {
				int target = transitions[c];
				Double prob = preImageList[target].get(source);
				if (prob==null) {
					prob=characterDist[c];
				} else {
					prob+=characterDist[c];
				}
				preImageList[target].put(source, prob);
			}
			++source;
		}
		
		int[][] preimage = new int[stateCount][];
		double[][] preimageProb = new double[stateCount][];
		for (int i=0; i<stateCount; ++i) {
			preimage[i]=new int[preImageList[i].size()];
			preimageProb[i]=new double[preImageList[i].size()];
			int j = 0;
			for (Entry<Integer,Double> e : preImageList[i].entrySet()) {
				preimage[i][j]=e.getKey();
				preimageProb[i][j]=e.getValue();
				++j;
			}
		}
		int[] emissions = new int[stateCount];
		int i=0;
		for (int emission : outputTable) {
			emissions[i]=emission;
			++i;
		}
		double[] emissionProbs = new double[stateCount];
		i=0;
		for (double p : outputProbabilities) {
			emissionProbs[i]=p;
			++i;
		}
		return new MarkovAdditiveChain(preimage, preimageProb, emissions, emissionProbs);
	}
	
	/** Returns an automaton recognizing the same language, but in a non-overlapping way. */
	// TODO: remove unreachable states
	public CDFA toNonOverlapping() {
		List<int[]> newTransitionTable = new ArrayList<int[]>(transitionTable.size());
		List<Integer> newOutputTable = new ArrayList<Integer>(outputTable.size());
		
		for (int state=0; state<transitionTable.size(); ++state) {
			int[] newTransitions = new int[alphabet.size()];
			if (outputTable.get(state)==0) {
				System.arraycopy(transitionTable.get(state), 0, newTransitions, 0, alphabet.size());
				newOutputTable.add(0);
			} else {
				System.arraycopy(transitionTable.get(0), 0, newTransitions, 0, alphabet.size());
				newOutputTable.add(1);
			}
			newTransitionTable.add(newTransitions);
		}
		
		return new CDFA(alphabet,newTransitionTable,newOutputTable);
	}
	
	/** Returns an automaton recognizing the same language, but returns match positions only (if
	 *  two matches end at the same position, only one is reported. */
	public CDFA toMatchPositionCount() {
		List<int[]> newTransitionTable = new ArrayList<int[]>(transitionTable.size());
		List<Integer> newOutputTable = new ArrayList<Integer>(outputTable.size());
		
		for (int state=0; state<transitionTable.size(); ++state) {
			if (outputTable.get(state)==0) {
				newOutputTable.add(0);
			} else {
				newOutputTable.add(1);
			}
			int[] newTransitions = new int[alphabet.size()];
			System.arraycopy(transitionTable.get(state), 0, newTransitions, 0, alphabet.size());
			newTransitionTable.add(newTransitions);
		}
		return new CDFA(alphabet,newTransitionTable,newOutputTable);
	}
	
	/** Returns a list of states that yield an output > 0. */
	public List<Integer> getOutputStates() {
		List<Integer> result = new ArrayList<Integer>();
		for (int i=0; i<outputTable.size(); ++i) {
			if (outputTable.get(i)>0) {
				result.add(i);
			}
		}
		return result;
	}
	
	public int getStateCount() {
		return outputTable.size();
	}
	
	public String toString() {
		StringBuffer sb = new StringBuffer();
		for (int node=0; node<outputTable.size(); ++node) {
			sb.append(String.format("%d(%d): ", node, outputTable.get(node)));
			for (int c=0; c<alphabet.size(); ++c) {
				char chr = alphabet.get(c);
				sb.append(String.format("%s-->%d, ", chr, transitionTable.get(node)[c]));
			}
			sb.append("\n");
		}
		return sb.toString();
	}
}
